Skip to main content

4-6 16. 最接近的三数之和

Date：2022-04-06 08:38:22

题目：16. 最接近的三数之和 ( 中等😕 )​

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例​

示例1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例2：

输入：nums = [0,0,0], target = 1
输出：0

分析​

题解​

排序+双指针

function threeSumClosest(nums: number[], target: number): number {
  const len = nums.length
  nums.sort((a, b) => a - b)

  let ans = Infinity,
      a = 0
  while (a < len) {
    while (a > 0 && nums[a] == nums[a - 1]) {
      ++a
    }

    let b = a + 1,
        c = len - 1
    while (b < c) {
      const sum = nums[a] + nums[b] + nums[c]

      if (sum === target) {
        return target
      }

      const diff = Math.abs(sum - target) < Math.abs(ans - target)
      ans = diff ? sum : ans

      if (sum > target) {
        --c

        while (c < len - 1 && b < c && nums[c] == nums[c + 1]) {
          --c
        }
      } else {
        ++b

        while (b > a + 1 && b < c && nums[b] == nums[b - 1]) {
          ++b
        }
      }
    }

    ++a
  }

  return ans
}

使用

function main() {
  const nums = [-1, 2, 1, -4],
        target = 1

  console.log('[]:', threeSumClosest(nums, target))
}

main()

export {}